Graph product

In mathematics, a graph product is a certain kind of binary operation on graphs. Specifically, it is an operation that takes two graphs G₁ and G₂ and produces a graph H with the following properties:

The vertex set of H is the Cartesian product V(G₁) × V(G₂), where V(G₁) and V(G₂) are the vertex sets of G₁ and G₂, respectively.
Two vertices (u₁, u₂) and (v₁, v₂) of H are connected by an edge if and only if the vertices u₁, u₂, v₁, v₂ satisfy conditions of a certain type (see below).

The following table shows the most common graph products, with ∼ denoting “is connected by an edge to”:

Name	Condition for (u₁, u₂) ∼ (v₁, v₂).	Dimensions
Cartesian product	( u₁ = v₁ and u₂ ∼ v₂ ) or ( u₁ ∼ v₁ and u₂ = v₂ )	$G_{V_1, E_1} \square H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 %2B E_1 V_2)}$
Tensor product	u₁ ∼ v₁ and u₂ ∼ v₂	$G_{V_1, E_1} \times H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (2 E_1 E_2)}$
Lexicographical product	u₁ ∼ v₁ or ( u₁ = v₁ and u₂ ∼ v₂ )	$G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 %2B E_1 V_2^2)}$
Strong product (Normal product, AND product)	( u₁ = v₁ and u₂ ∼ v₂ ) or ( u₁ ∼ v₁ and u₂ = v₂ ) or ( u₁ ∼ v₁ and u₂ ∼ v₂ )	$G_{V_1, E_1} \boxtimes H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (V_1 E_2 %2B V_2E_1 %2B 2 E_1 E_2)}$
Co-normal product (disjunctive product, OR product)	u₁ ∼ v₁ or u₂ ∼ v₂
Rooted product	see article	$G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 %2B E_1)}$

In general, a graph product is determined by any condition for (u₁, u₂) ∼ (v₁, v₂) that can be expressed in terms of the statements u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁, and u₂ = v₂.

References

Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8 .

Graph product

See also

References